package link;


import org.junit.Test;


public class UnionTwoLink {

    //数组去重 设置一个指针定义,两个
    @Test
    public void testOrderOne() {
        int[] arr1 = {1, 7, 8};
        int[] arr2 = {1, 2, 7, 8, 9, 10, 22};
        int[] arr3 = new int[arr1.length + arr2.length];
        int index = 0;
        //        while(index<arr1.length&&index<arr2.length){
        //            if(arr1[index]<=arr2[index]){
        //                arr3[index]=arr1[index];
        //            }else {
        //                arr3[index]=arr2[index];
        //            }
        //                 index++;
        // }
        while(index<arr1.length&&index<arr2.length) {
            arr3[index] = arr1[index] < arr2[index] ? arr1[index] : arr2[index];
            index++;
        }

        if(index>=arr1.length){ //先遍历完了arr1,继续添加arr2
         //就循环添加
            while(index<arr2.length){
                arr3[index]=arr2[index];
                index++;
            }
        }else{
            while(index<arr1.length){
                arr3[index]=arr1[index];
                index++;
            }
        }
        for (int i = 0; i <index; i++) {
            System.out.println(arr3[i]);
        }

    }

    //1.合并两个有序表(数组+链表)
    @Test //数组
    public void testArrayUnion(){
        int[] arr2={1,7,8};
        int[]arr1={1,2,7,8,9,10,22};
        int[]arr3=new int[arr1.length+arr2.length];
        int index=0;
        int index1=0;
        int index2=0;
        while(index1<arr1.length&&index2<arr2.length){
            if(arr1[index1]<=arr2[index2]){
                arr3[index]=arr1[index1];
                index++;
                index1++;
            }else {
                arr3[index]=arr2[index2];
                index++;
                index2++;
            }
            //            arr3[index]=arr1[index]<arr2[index]?arr1[index]:arr2[index];
            //            index++;
        }

        if(index1>=arr1.length){ //先遍历完了arr1,继续添加arr2
            //就循环添加
            while(index2<arr2.length){
                arr3[index]=arr2[index2];
                index2++;
                index++;
            }
        }else{//先遍历完了arr2,继续添加arr1
            while(index1<arr1.length){
                arr3[index]=arr1[index1];
                index1++;
                index++;
            }
        }
        for (int i = 0; i <arr3.length; i++) {
            System.out.println(arr3[i]);
        }

    }

    @Test //链表
    public void testLinkUnion(){
        //两个有序单链表合并(不按照顺序)
        SingLinkListUnion singLinkList1=new SingLinkListUnion();
        SingLinkPool s1=new SingLinkPool(1);
        SingLinkPool s2=new SingLinkPool(7);
        SingLinkPool s3=new SingLinkPool(8);
        singLinkList1.add(s1);
        singLinkList1.add(s2);
        singLinkList1.add(s3);
        SingLinkListUnion singLinkList2=new SingLinkListUnion();
        SingLinkPool s4=new SingLinkPool(1);
        SingLinkPool s5=new SingLinkPool(7);
        SingLinkPool s6=new SingLinkPool(8);
        SingLinkPool s7=new SingLinkPool(17);
        SingLinkPool s8=new SingLinkPool(4);
        SingLinkPool s9=new SingLinkPool(88);
        singLinkList2.add(s4);
        singLinkList2.add(s5);
        singLinkList2.add(s6);
        singLinkList2.add(s7);
        singLinkList2.add(s8);
        singLinkList2.add(s9);
        //合并到新链表
        System.out.println("链表1:");
        singLinkList1.show();
        System.out.println("链表2:");
        singLinkList2.show();
        //数据初始化完毕
        //定义链表一指针，和链表二指针
        SingLinkPool index1=singLinkList1.getHead();
        SingLinkPool index2=singLinkList2.getHead();
        //不能和前面数组一样方式，要不然每次都要new SingLinkPool()添加到新链表内,否则抛出空指针异常
        SingLinkPool index3=index1; //假设index3->index1 || index3->index2 都可以
        //
        while((index1=index1.next)!=null){
            index3=index3.next;
            index3.data=index1.data;
        }
        while((index2=index2.next)!=null){
            index3.next=index2;
            index3=index3.next;
        }
        System.out.println("新链表:");
        singLinkList1.show();


    }


    // 2.按递增顺序合并两个递增顺序有序表(数组+链表)
    //数组实现
    @Test
    public void testIncrementArrayUnion(){
        int[] arr1 = {1, 3,7, 8, 8,10};
        int[] arr2 = {1, 2, 7, 8, 9,9,10, 22};
        int[] arr3 = new int[arr1.length + arr2.length];
        //思路: 1.先遍历arr1 如果arr1中小于arr2中数就添加到arr3
        //2.反之比arr2中大,就再去遍历arr2，谁小谁先添加进arr3
        int index1=0;
        int index2=0;
        int index=0;
        //必须加上判断条件  要不然去下一个while循环 会数组越界
        while(index1<arr1.length&&index2<arr2.length){
                while(index1<arr1.length&&index2<arr2.length&&arr1[index1]<=arr2[index2]){
                    arr3[index]=arr1[index1]; //添加完后index=3
                    index++;
                    index1++;
                }
                //arr1[3]越界
                while (index1<arr1.length&&index2<arr2.length&&arr1[index1]>arr2[index2]){
                    arr3[index]=arr2[index2];
                    index++;index2++;
                }
        }
        //其中一个遍历完了就跳出循环
        if(index1>=arr1.length){ //arr1遍历完了，再依次把arr2中的数据添加到arr3中
            while(index2<arr2.length){
                arr3[index++]=arr2[index2++];
            }
        }else{ //反之 把arr1剩余的数据添加到arr3中
            while(index1<arr1.length){
                arr3[index++]=arr1[index1++];
            }
        }
        System.out.println("排序后:");
        for (int i = 0; i <arr3.length ; i++) {
            System.out.printf("arr[%d]=%d\t",i,arr3[i]);
        }
    }
    //链表实现
    @Test
    public void testIncrementLinkUnion(){
        //两个有序单链表合并(不按照顺序)
        SingLinkListUnion singLinkList1=new SingLinkListUnion();
        SingLinkPool s1=new SingLinkPool(1);
        SingLinkPool s2=new SingLinkPool(2);
        SingLinkPool s3=new SingLinkPool(8);
        singLinkList1.add(s1);
        singLinkList1.add(s2);
        singLinkList1.add(s3);
        SingLinkListUnion singLinkList2=new SingLinkListUnion();
        SingLinkPool s4=new SingLinkPool(1);
        SingLinkPool s5=new SingLinkPool(3);
        SingLinkPool s6=new SingLinkPool(8);
        SingLinkPool s7=new SingLinkPool(8);
        SingLinkPool s8=new SingLinkPool(10);
        SingLinkPool s9=new SingLinkPool(88);
        singLinkList2.add(s4);
        singLinkList2.add(s5);
        singLinkList2.add(s6);
        singLinkList2.add(s7);
        singLinkList2.add(s8);
        singLinkList2.add(s9);
        //合并到新链表
        System.out.println("链表1:");
        singLinkList1.show();
        System.out.println("链表2:");
        singLinkList2.show();
        //数据初始化完毕
        //定义链表一指针，和链表二指针
        SingLinkPool index1=singLinkList1.getHead().next; //指针一
        SingLinkPool index2=singLinkList2.getHead().next; //指针二
        SingLinkPool temp=index1; //定义一个赋值指针
        //如果temp=index2  逻辑就要反过来处理
        //不能直接跳，再判断
        while(index1!=null||index2!=null){
            if(index1.data<= index2.data&&index1==temp){
                if(index1.next!=null){
                    temp=index1.next;
                    index1.next=index2;
                    index1=temp;
                    temp=index2;
                }else{
                    index1.next=index2;
                    break;
                }
            }else{
                if(index2.next!=null){
                    temp=index2.next;
                    index2.next=index1;
                    index2=temp;
                    temp=index1;
                }else{
                    index2.next=index1;
                    break;
                }
            }
        }

        System.out.println("新链表:");
        singLinkList1.show();
    }

}

class SingLinkListUnion{
    SingLinkPool head=new SingLinkPool();//定义头节点

    public SingLinkPool getHead() {
        return head;
    }

    //向链表尾部添加
    public void add(SingLinkPool singLinkPool){
        SingLinkPool temp=head;
        while(temp.next!=null){
            temp=temp.next;
        }
        //当temp.next指向空时跳出循环
        temp.next=singLinkPool;
    }
    //遍历链表
    public void  show(){
        SingLinkPool temp=head.next;
        if(temp==null){
            System.out.println("链表为空~ ~");
            return;
        }
        while(temp!=null){
            System.out.println(temp.toString());
            temp=temp.next;
        }
    }
}
//定义单链表结构
class SingLinkPool{
    public int data; //值
    public SingLinkPool next;
    public SingLinkPool() { }
    public SingLinkPool(int data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "SingLinkPool{" + "data=" + data + '}';
    }
}
